/LMAR=0/XLINE=3/USET=43␈↓ α,␈↓␈↓ ⊂F1


␈↓ α,␈↓α␈↓ ε8FINITE STATE SEARCH PROBLEMS




␈↓ α,␈↓α␈↓ εUJohn McCarthy, Stanford University




␈↓ α,␈↓α1. Introduction

␈↓ α,␈↓␈↓ α|We␈α⊂have␈α⊂found␈α⊂a␈α⊂class␈α⊂of␈α⊂search␈α⊂problems␈α⊂that␈α⊂may␈α⊂admit␈α⊂very␈α⊂e≠cient␈α⊂algorithms␈α⊂and␈α⊂to
␈↓ α,␈↓which␈α⊗many␈α⊗search␈α⊗problems␈α⊗that␈α⊗arise␈α⊗naturally␈α⊗can␈α⊗be␈α⊗reduced.␈α⊗ The␈α⊗reduction␈α⊗itself␈α⊗will
␈↓ α,␈↓often␈α∪be␈α∪a␈α∪more␈α∪di≠cult␈α∪heuristic␈α∪problem␈α∪than␈α∪the␈α∪subsequent␈α∪solution,␈α∪but␈α∪nevertheless␈α∪this
␈↓ α,␈↓way of dividing problems may often be the best way of conquering them.

␈↓ α,␈↓␈↓ α|The␈α∩methods␈α∩to␈α∩be␈α∩described␈α∩are␈α∩applicable␈α∩to␈α∩what␈α∩I␈α∩want␈α∩to␈α∩call␈α∩␈↓↓non-mental␈α∩quasi-static
␈↓ α,␈↓↓problems␈↓.␈α⊃ "Quasi-static"␈α⊃means␈α⊃that␈α⊃each␈α⊃action␈α⊃of␈α⊃the␈α⊃problem␈α⊃solver␈α⊃gives␈α⊃rise␈α⊃to␈α⊃a␈α⊃new␈α⊃state,
␈↓ α,␈↓and␈α⊃the␈α⊃problem␈α⊃is␈α⊃to␈α⊃≡nd␈α⊃a␈α⊃sequence␈α⊃of␈α⊃actions␈α⊃leading␈α⊃from␈α⊃an␈α⊃initial␈α⊃state␈α⊃to␈α⊃a␈α⊃state␈α⊃having
␈↓ α,␈↓desired␈α∩properties.␈α∩ "Non-mental"␈α∩means␈α∩that␈α∩the␈α∩problem␈α⊃is␈α∩to␈α∩be␈α∩solved␈α∩with␈α∩the␈α∩information
␈↓ α,␈↓provided;␈α⊂strategies␈α⊂to␈α⊂acquire␈α⊂additional␈α⊂information␈α⊂from␈α⊂the␈α⊂external␈α⊂world␈α⊂are␈α⊂not␈α⊂required,
␈↓ α,␈↓although␈α≠conclusions␈α≠may␈α≠have␈α≠to␈α≠be␈α≠deduced.␈α≠ Almost␈α≠all␈α≠of␈α≠the␈α≠problems␈α≠solved␈α≠using
␈↓ α,␈↓STRIPS and PLANNER and CONNIVER are quasi-static, and most of them are non-mental.

␈↓ α,␈↓␈↓ α|␈↓↓Finite␈α⊂state␈α⊂search␈α⊂problems␈↓␈α⊂have␈α⊂␈↓↓Boolean␈α⊂search␈α⊂problems␈↓␈α⊂as␈α⊂an␈α⊂important␈α⊂subclass.␈α⊂ These
␈↓ α,␈↓are formulated as follows:

␈↓ α,␈↓␈↓ α|The␈α∀state␈α∀of␈α∀the␈α∀system␈α∀is␈α∀characterized␈α∀by␈α∀the␈α∀values␈α∀of␈α∀Boolean␈α∀variables␈α∀␈↓↓p␈↓β1␈↓,...,␈↓↓p␈↓βn␈↓.␈α∀ An
␈↓ α,␈↓allowed transformation of state is represented by a formula such as

␈↓ α,␈↓␈↓ α|␈↓↓p␈↓β1␈↓↓∧␈↓λ-␈↓↓p␈↓β2␈↓↓∧␈↓λ-␈↓↓p␈↓β3␈↓↓∧p␈↓β4␈↓ => ␈↓↓p␈↓β3␈↓↓∧␈↓λ-␈↓↓p␈↓β4␈↓↓∧p␈↓β6␈↓.

␈↓ α,␈↓The␈α∩meaning␈α∩of␈α∩the␈α∩formula␈α∩is␈α∩that␈α∩if␈α∩a␈α∩state␈α∩satis≡es␈α∩the␈α∩premiss␈α∩of␈α∩the␈α∩transformation,␈α∩then
␈↓ α,␈↓the␈α⊂transformation␈α⊂takes␈α⊂it␈α⊂into␈α⊂a␈α⊂state␈α⊂satisfying␈α⊂the␈α⊂conclusion,␈α⊂where␈α⊂unmentioned␈α⊂␈↓↓p␈↓'s␈α⊂are␈α⊂left
␈↓ α,␈↓unchanged.

␈↓ α,␈↓␈↓ α|The desired state is characterized by a similar formula.

␈↓ α,␈↓␈↓ α|There␈α⊂is␈α⊂a␈α⊂straightforward␈α⊂breadth␈α⊂≡rst␈α⊂search␈α⊂algorithm␈α⊂for␈α⊂a␈α⊂sequence␈α⊂of␈α⊂transformations
␈↓ α,␈↓leading␈α⊃to␈α⊃the␈α⊃desired␈α⊃≡nal␈α⊃state.␈α⊃ It␈α⊃represents␈α⊃a␈α⊃state␈α⊃by␈α⊃a␈α⊃Boolean␈α⊃vector,␈α⊃e.g.␈α⊃by␈α⊃the␈α⊃bits␈α⊃in␈α⊃a
␈↓ α,␈↓machine␈α⊂word.␈α⊂ The␈α⊂transformation␈α⊂is␈α⊂represented␈α⊂by␈α⊂four␈α⊂Boolean␈α⊂words,␈α⊂a␈α⊂mask␈α⊂each␈α⊂for␈α⊂the
␈↓ α,␈↓left␈α∂and␈α∂right␈α∂parts␈α∂and␈α∂vectors␈α∂whose␈α∂ones␈α∂correspond␈α∂to␈α∂the␈α∂unnegated␈α∂propositional␈α∂variables
␈↓ α,␈↓in␈α∩the␈α∩left␈α∩and␈α∩right␈α∩parts.␈α∩ If␈α∩the␈α∩state␈α∩is␈α∩denoted␈α∩by␈α∩␈↓↓s,␈↓␈α∩the␈α∩masks␈α∩by␈α∩␈↓↓m␈↓βL␈↓␈α∩and␈α∩␈↓↓m␈↓βR␈↓␈α∩respectively,
␈↓ α,␈↓and␈α⊂the␈α⊂left␈α⊂and␈α⊂right␈α⊂parts␈α⊂by␈α⊂␈↓↓L␈↓␈α⊂and␈α⊂␈↓↓R␈↓␈α⊂respectively,␈α⊂then␈α⊂the␈α⊂condition␈α⊂for␈α⊂applicability␈α⊂of␈α⊂the
␈↓ α,␈↓transformation is

␈↓ α,␈↓␈↓ α|␈↓↓m␈↓βL␈↓ ∧ ␈↓↓s␈↓ = ␈↓↓L␈↓


␈↓ α,␈↓and the state resulting from the transformation is
␈↓ α,␈↓Finitary Search␈↓ 	␈↓αDraft␈↓␈↓ ∞September 5, 1989


␈↓ α,␈↓␈↓ α|(␈↓↓m␈↓βR␈↓ ∧ ␈↓↓s␈↓ ) ∨ ␈↓↓R␈↓ ,


␈↓ α,␈↓assuming the logical operators are given a bitwise interpretation.

␈↓ α,␈↓Therefore,␈α⊗a␈α⊗transformation␈α⊗can␈α⊗be␈α⊗applied␈α⊗to␈α⊗a␈α⊗state␈α⊗in␈α⊗a␈α⊗few␈α⊗machine␈α⊗instructions,␈α⊗and␈α⊗it
␈↓ α,␈↓seems␈α∂that␈α∂problems␈α∂involving␈α∂up␈α∂to␈α∂say␈α∂twenty␈α∂Boolean␈α∂variables␈α∂can␈α∂be␈α∂done␈α∂in␈α∂a␈α∂few␈α∂seconds
␈↓ α,␈↓by␈α⊂a␈α⊂program␈α⊂whose␈α⊂basic␈α⊂loop␈α⊂computes␈α⊂the␈α⊂successors␈α⊂of␈α⊂the␈α⊂newly␈α⊂found␈α⊂states␈α⊂and␈α⊂sorts␈α⊂the
␈↓ α,␈↓newly␈α∪found␈α∪states␈α∪against␈α∪the␈α∪set␈α∪of␈α∪all␈α∪states␈α∪found␈α∪so␈α∪far␈α∪in␈α∪order␈α∪to␈α∪discard␈α∪old␈α∪states.␈α∪ (If
␈↓ α,␈↓previously␈α↔found␈α↔states␈α↔are␈α↔not␈α↔discarded,␈α↔then␈α↔the␈α↔algorithm␈α↔will␈α↔blow␈α↔up␈α↔on␈α↔rather␈α↔small
␈↓ α,␈↓problems).␈α∂ The␈α∂algorithm␈α∂will␈α∂usually␈α∂run␈α∂out␈α∂of␈α∂main␈α∂memory␈α∂before␈α∂it␈α∂runs␈α∂out␈α∂of␈α∂time,␈α∂so␈α∂it
␈↓ α,␈↓may be worthwhile to work out variants of the algorithm that use secondary storage.

␈↓ α,␈↓␈↓ α|In␈α↔the␈α↔general␈α↔form␈α↔of␈α↔the␈α↔≡nite␈α↔state␈α↔search␈α↔problem,␈α↔the␈α↔state␈α↔is␈α↔characterized␈α↔by␈α↔the
␈↓ α,␈↓values␈α⊗of␈α⊗a␈α⊗number␈α⊗of␈α⊗variables␈α⊗each␈α⊗taking␈α⊗values␈α⊗in␈α⊗small␈α⊗≡nite␈α⊗sets.␈α⊗ For␈α⊗example,␈α⊗there
␈↓ α,␈↓might␈α⊃be␈α⊃variables␈α⊃␈↓↓x␈↓β1␈↓,...,␈↓↓x␈↓β5␈↓,␈α⊃where␈α⊃␈↓↓x␈↓β1␈↓␈α⊃takes␈α⊃the␈α⊃values␈α⊃0,...,4,␈α⊃and␈α⊃␈↓↓x␈↓β2␈↓␈α⊃takes␈α⊃values␈α⊃0,...,7,␈α⊃etc.␈α⊃ The
␈↓ α,␈↓premiss of a transformation is a conjunction such as

␈↓ α,␈↓␈↓ α|␈↓↓x␈↓β1␈↓=3∧␈↓↓x␈↓β2␈↓≠1∧␈↓↓x␈↓β4␈↓=3,


␈↓ α,␈↓and the conclusion is a collection of assignments such as

␈↓ α,␈↓␈↓ α|␈↓↓x␈↓β1␈↓←2;␈↓↓x␈↓β3␈↓←4;␈↓↓x␈↓β5␈↓←0.

␈↓ α,␈↓The␈α↔transformations␈α↔are␈α↔interpreted␈α↔just␈α↔as␈α↔in␈α↔the␈α↔Boolean␈α↔case,␈α↔i.e.␈α↔ if␈α↔a␈α↔state␈α↔satis≡es␈α↔the
␈↓ α,␈↓premiss␈α∩of␈α∩the␈α∩transformation,␈α∩it␈α∩can␈α∩be␈α∩transformed␈α∩by␈α∩making␈α∩the␈α∩assignment␈α∩speci≡ed␈α∩in␈α∩its
␈↓ α,␈↓conclusion.

␈↓ α,␈↓␈↓ α|There␈α∩is␈α∩also␈α∩a␈α∩fast␈α∩␈↓↓standard␈↓␈α∩␈↓↓algorithm␈↓␈α∩for␈α∩the␈α∩general␈α∩case␈α∩of␈α∩≡nite␈α∩state␈α∩search.␈α∩ It␈α∩packs
␈↓ α,␈↓the␈α⊂values␈α⊂of␈α⊂the␈α⊂state␈α⊂variables␈α⊂into␈α⊂a␈α⊂machine␈α⊂word␈α⊂leaving␈α⊂an␈α⊂unused␈α⊂␈↓↓guard␈↓␈α⊂␈↓↓bit␈↓␈α⊂between␈α⊂the
␈↓ α,␈↓strings␈α~of␈α~bits␈α~representing␈α~the␈α~components.␈α~ The␈α~premiss␈α~of␈α~a␈α~transformation␈α~is␈α~tested␈α~in
␈↓ α,␈↓parallel␈α⊂in␈α⊂the␈α⊂following␈α⊂way:␈α⊂First␈α⊂we␈α⊂␈↓↓and␈↓␈α⊂the␈α⊂state␈α⊂with␈α⊂a␈α⊂mask␈α⊂that␈α⊂has␈α⊂all␈α⊂␈↓αone␈↓'s␈α⊂in␈α⊂the␈α⊂≡elds
␈↓ α,␈↓coresponding␈α↔to␈α↔the␈α↔variables␈α↔subjected␈α↔to␈α↔conditions.␈α↔ We␈α↔then␈α↔␈↓↓exclusive␈↓␈α↔␈↓↓or␈↓␈α↔with␈α↔the␈α↔word
␈↓ α,␈↓representing␈α∀the␈α∀right␈α∀hand␈α∀sides␈α∀of␈α∀the␈α∀conditions␈α∀of␈α∀the␈α∀premiss,␈α∀so␈α∀that␈α∀the␈α∀new␈α∀word␈α∀has
␈↓ α,␈↓␈↓αzero␈↓'s␈α∩in␈α∩precisely␈α∩those␈α∩≡elds␈α∩where␈α∩the␈α∩components␈α∩of␈α∩the␈α∩state␈α∩equal␈α∩the␈α∩right␈α∩hand␈α∩sides␈α∩of
␈↓ α,␈↓the␈α∂conditions.␈α∂ Next␈α∂we␈α∂␈↓↓add␈↓␈α∂a␈α∂word␈α∂with␈α∂all␈α∂␈↓αone␈↓'s␈α∂in␈α∂those␈α∂≡elds,␈α∂getting␈α∂a␈α∂carry␈α∂into␈α∂the␈α∂guard
␈↓ α,␈↓bits␈α⊂where␈α⊂the␈α⊂equalities␈α⊂are␈α⊂not␈α⊂satis≡ed.␈α⊂ Now␈α⊂we␈α⊂mask␈α⊂out␈α⊂all␈α⊂but␈α⊂the␈α⊂guard␈α⊂bits␈α⊂and␈α⊂test␈α⊂for
␈↓ α,␈↓equality␈α⊃with␈α⊃a␈α⊃word␈α⊃that␈α⊃has␈α⊃␈↓αone␈↓'s␈α⊃in␈α⊃precisely␈α⊃those␈α⊃guard␈α⊃bits␈α⊃where␈α⊃inequality␈α⊃was␈α⊃wanted.
␈↓ α,␈↓If␈α⊂the␈α⊂condition␈α⊂is␈α⊂satis≡ed,␈α⊂making␈α⊂the␈α∂transformation␈α⊂is␈α⊂just␈α⊂a␈α⊂matter␈α⊂of␈α⊂masking␈α⊂out␈α⊂the␈α⊂≡elds
␈↓ α,␈↓to which assignments are made and ␈↓↓or␈↓ing in the right hand sides of the assignments.


␈↓ α,␈↓α2. Examples

␈↓ α,␈↓␈↓ α|1.␈α↔Suppose␈α↔there␈α↔are␈α↔four␈α↔blocks␈α↔called␈α↔␈↓↓A,␈↓␈α↔␈↓↓B,␈↓␈α↔␈↓↓C,␈↓␈α↔and␈α↔␈↓↓D␈↓␈α↔on␈α↔a␈α↔table,␈α↔and␈α↔that␈α↔a␈α↔state␈α↔is
␈↓ α,␈↓characterized␈α⊃by␈α⊃the␈α⊃set␈α⊃of␈α⊃relations␈α⊃of␈α⊃the␈α⊃form␈α⊃␈↓↓on(x,y)␈↓␈α⊃that␈α⊃are␈α⊃satis≡ed.␈α⊃ Since␈α⊃there␈α⊃are␈α⊃four
␈↓ α,␈↓blocks␈α⊂each␈α⊂of␈α⊂which␈α⊂can␈α⊂be␈α⊂on␈α⊂any␈α⊂of␈α⊂the␈α⊂other␈α⊂blocks␈α⊂or␈α⊂the␈α⊂table,␈α⊂the␈α⊂state␈α⊂is␈α⊂determined␈α⊂by
␈↓ α,␈↓the␈α∂values␈α∂of␈α∂16␈α∂Boolean␈α∂variables.␈α∂ If␈α∂we␈α∂have␈α∂␈↓↓p␈↓β1␈↓↓␈α∂=␈α∂on(A,B),␈α∂p␈↓β2␈↓↓␈α∂=␈α∂on(A,C),␈α∂p␈↓β3␈↓↓␈α∂=␈α∂on(A,D),␈α∂p␈↓β4␈↓↓␈α∂=
␈↓ α,␈↓↓on(A,Table), p␈↓β5␈↓↓ = on(B,A)␈↓, etc. in the obvious way, then the allowed transformations are
␈↓ α,␈↓Finitary Search␈↓ 	␈↓αDraft␈↓␈↓ ∞September 5, 1989


␈↓ α,␈↓␈↓ α|␈↓λ-␈↓␈↓↓p␈↓β5␈↓∧␈↓λ-␈↓␈↓↓p␈↓β9␈↓∧␈↓λ-␈↓␈↓↓p␈↓β13␈↓∧␈↓λ-␈↓␈↓↓p␈↓β10␈↓∧␈↓λ-␈↓␈↓↓p␈↓β14␈↓ => ␈↓↓p␈↓β1␈↓∧␈↓λ-␈↓␈↓↓p␈↓β2␈↓∧␈↓λ-␈↓␈↓↓p␈↓β3␈↓∧␈↓λ-␈↓␈↓↓p␈↓β4␈↓, etc. -

␈↓ α,␈↓one␈α⊗transformation␈α⊗giving␈α⊗the␈α⊗conditions␈α⊗for␈α⊗putting␈α⊗each␈α⊗block␈α⊗on␈α⊗each␈α⊗other␈α⊗or␈α⊗the␈α⊗table.
␈↓ α,␈↓While␈α∃there␈α∃are␈α∃2␈↓∧16␈↓␈α∃=␈α∃65536␈α∃states,␈α∃only␈α∃4␈↓∧4␈↓␈α∃=␈α∃256␈α∃of␈α∃them␈α∃are␈α∃legitimate␈α∃since␈α∃a␈α∃block␈α∃is␈α∃in
␈↓ α,␈↓exactly␈α∪one␈α∪place␈α∪in␈α∪any␈α∪given␈α∪state.␈α∪ Therefore,␈α∪the␈α∪search␈α∪for␈α∪a␈α∪path␈α∪to␈α∪a␈α∪goal␈α∪will␈α∪be␈α∪quite
␈↓ α,␈↓fast.

␈↓ α,␈↓␈↓ α|The␈α∪same␈α∪problem␈α∪can␈α∪be␈α∪represented␈α∪as␈α∪a␈α∪≡nite␈α∪state␈α∪search␈α∪problem␈α∪by␈α∪introducing␈α∪the
␈↓ α,␈↓variables␈α∂␈↓↓x␈↓β1␈↓,...,␈↓↓x␈↓β4␈↓␈α∂each␈α∂taking␈α∂the␈α∂values␈α∂0␈α∂through␈α∂4␈α∂and␈α∂giving␈α∂the␈α∂block␈α∂or␈α∂table␈α∂that␈α∂supports
␈↓ α,␈↓each␈α∪block␈α∪and␈α∪therefore␈α∪5␈↓∧4␈↓␈α∪=␈α∪625␈α∪states.␈α∪ If␈α∪we␈α∪use␈α∪a␈α∪di≥erent␈α∪space␈α∪for␈α∪the␈α∪support␈α∪of␈α∪each
␈↓ α,␈↓block,␈α∪then␈α∪we␈α∪are␈α∪down␈α∪to␈α∪the␈α∪minimum␈α∪256␈α∪states.␈α∪ Naturally,␈α∪if␈α∪a␈α∪human␈α∪is␈α∪setting␈α∪up␈α∪the
␈↓ α,␈↓problem,␈α⊗this␈α⊗is␈α⊗the␈α⊗right␈α⊗thing␈α⊗to␈α⊗do,␈α⊗but␈α⊗if␈α⊗a␈α⊗program␈α⊗is␈α⊗generating␈α⊗the␈α⊗≡nite␈α⊗state␈α⊗search
␈↓ α,␈↓problem␈α∀from␈α∀the␈α∀problem␈α∀expressed␈α∀in␈α∀a␈α∀di≥erent␈α∀formalism,␈α∀we␈α∀may␈α∀still␈α∀get␈α∀a␈α∀good␈α∀result
␈↓ α,␈↓even if it misses the fact that a block cannot be on top of itself.

␈↓ α,␈↓␈↓ α|Again␈α∩there␈α∩are␈α∩sixteen␈α∩transformations,␈α∩and␈α∩the␈α∩one␈α∩corresponding␈α∩to␈α∩the␈α∩above␈α∩Boolean
␈↓ α,␈↓transformation is

␈↓ α,␈↓␈↓ α|␈↓↓x␈↓β2␈↓≠1 ∧ ␈↓↓x␈↓β3␈↓l≠1 ∧ ␈↓↓x␈↓β4␈↓≠1 ∧ ␈↓↓x␈↓β3␈↓≠2 ∧ ␈↓↓x␈↓β4␈↓≠2 => ␈↓↓x␈↓β1␈↓ ← 2.

␈↓ α,␈↓␈↓ α|Unfortunately,␈α~the␈α~standard␈α~algorithm␈α→for␈α~≡nite␈α~state␈α~search␈α~won't␈α~work␈α~for␈α~the␈α~block
␈↓ α,␈↓moving␈α⊂problem,␈α⊂because␈α⊂the␈α⊂variable␈α⊂␈↓↓x␈↓β3␈↓,␈α⊂for␈α∂example,␈α⊂must␈α⊂satisfy␈α⊂two␈α⊂inequality␈α⊂conditions␈α⊂in
␈↓ α,␈↓the␈α⊂≡rst␈α⊂transformation.␈α⊂ This␈α⊂can␈α⊂be␈α⊂≡xed␈α⊂by␈α⊂representing␈α⊂each␈α⊂variable␈α⊂twice,␈α⊂and␈α⊂everything
␈↓ α,␈↓will still ≡t in a machine word.

␈↓ α,␈↓␈↓ α|2.␈α⊃The␈α⊃second␈α⊃example␈α⊃is␈α⊃the␈α⊃␈↓↓Tower␈α⊃of␈α⊃Hanoi␈↓␈α⊃problem.␈α⊃ There␈α⊃is␈α⊃a␈α⊃variable␈α⊃for␈α⊃each␈α⊃disk
␈↓ α,␈↓taking␈α⊃value␈α⊃1,␈α⊃2,␈α⊃or␈α⊃3␈α⊃stating␈α⊃what␈α⊃spike␈α⊃it␈α⊃is␈α⊃on.␈α⊃ A␈α⊃twelve␈α⊃disk␈α⊃state␈α⊃is␈α⊃representable␈α⊃in␈α⊃a␈α⊃36
␈↓ α,␈↓bit␈α∩word,␈α∩and␈α∩there␈α∩are␈α∩3␈↓∧12␈↓␈α∩=␈α∩531441␈α∩states␈α∩to␈α∩be␈α∩searched␈α∩so␈α∩the␈α∩problem␈α∩is␈α∩quite␈α∩feasible␈α∩by
␈↓ α,␈↓this brute force method.


␈↓ α,␈↓α3. Improved Algorithms

␈↓ α,␈↓␈↓ α|The␈α∀standard␈α∀algorithms␈α∀for␈α∀Boolean␈α∀or␈α∀≡nite␈α∀state␈α∀search␈α∀may␈α∀be␈α∀the␈α∀best␈α∀algorithm␈α∀in
␈↓ α,␈↓general␈α∃although␈α∃I␈α∃doubt␈α∃it.␈α∃ However,␈α∃it␈α∃would␈α∃seem␈α∃that␈α∃most␈α∃problems␈α∃arising␈α∃in␈α∃AI␈α∃will
␈↓ α,␈↓have structures that permit heuristics that greatly reduce the search.

␈↓ α,␈↓␈↓ α|The␈α∩≡nite␈α∩state␈α∩search␈α∩algorithm␈α∩can␈α∩be␈α∩improved␈α∩by␈α∩generalizing␈α∩the␈α∩conditions␈α∩that␈α∩can
␈↓ α,␈↓serve␈α∪as␈α∪premisses.␈α∪ There␈α∪is␈α∪no␈α∪point␈α∪in␈α∪introducing␈α∪disjunctions␈α∪as␈α∪well␈α∪as␈α∪conjunctions␈α∪into
␈↓ α,␈↓the␈α⊗premiss␈α⊗because␈α⊗this␈α⊗is␈α⊗handled␈α⊗by␈α⊗having␈α⊗a␈α⊗collection␈α⊗of␈α⊗rules␈α⊗-␈α⊗one␈α⊗for␈α⊗each␈α⊗disjunct.
␈↓ α,␈↓However,␈α∞we␈α∂can␈α∂allow␈α∂ranges␈α∂of␈α∂values␈α∂for␈α∞the␈α∂variables.␈α∂ It␈α∂is␈α∂necessary␈α∂only␈α∂to␈α∂choose␈α∂suitable
␈↓ α,␈↓constants␈α∀represent␈α∀the␈α∀value␈α∀of␈α∀each␈α∀variable␈α∀twice␈α∀by␈α∀the␈α∀contents␈α∀of␈α∀≡eld␈α∀in␈α∀the␈α∀word␈α∀and
␈↓ α,␈↓choose␈α↔suitable␈α↔constants␈α↔to␈α↔be␈α↔added␈α↔to␈α↔the␈α↔≡elds.␈α↔ Then␈α↔the␈α↔values␈α↔of␈α↔the␈α↔guard␈α↔bits␈α↔tell
␈↓ α,␈↓whether␈α∪the␈α∪addition␈α∪produced␈α∪over∨ow␈α∪and␈α∪after␈α∪masking␈α∪out␈α∪all␈α∪but␈α∪certain␈α∪guard␈α∪bits,␈α∪the
␈↓ α,␈↓program␈α∀can␈α∀test␈α∀for␈α∀equality␈α∀with␈α∀a␈α∀suitable␈α∀constant.␈α∀ I␈α∀don't␈α∀yet␈α∀have␈α∀examples␈α∀where␈α∀this
␈↓ α,␈↓pays o≥.

␈↓ α,␈↓␈↓ α|A␈α≠second␈α≠possible␈α≠improvement␈α≠involves␈α≠arranging␈α≠the␈α≠transformations␈α≠into␈α≠a␈α≠tree␈α≠of
␈↓ α,␈↓conditions, so that certain transformations are tested only if suitable conditions are satis≡ed.
␈↓ α,␈↓Finitary Search␈↓ 	␈↓αDraft␈↓␈↓ ∞September 5, 1989


␈↓ α,␈↓␈↓ α|The␈α⊂above␈α⊂improvements␈α⊂don't␈α⊂change␈α⊂the␈α⊂search␈α⊂space;␈α⊂they␈α⊂merely␈α⊂reduce␈α⊂the␈α⊂number␈α⊂of
␈↓ α,␈↓transformations.␈α⊂ However,␈α⊂the␈α⊂␈↓↓Tower␈α⊂of␈α⊂Hanoi␈↓␈α⊂problem␈α⊂is␈α⊂reduced␈α⊂by␈α⊂a␈α⊂heuristic␈α⊂that␈α⊂seems␈α⊂to
␈↓ α,␈↓have␈α_wide␈α_applicability.␈α_ Namely␈α_the␈α_bottom␈α_disk␈α_has␈α_to␈α_be␈α_moved,␈α_and␈α_the␈α_condition␈α_for
␈↓ α,␈↓moving␈α∪it␈α∪is␈α∪that␈α∪none␈α∪of␈α∪the␈α∪other␈α∪disks␈α∪be␈α∪on␈α∪it␈α∪or␈α∪on␈α∪its␈α∪destination␈α∪spike.␈α∪ Therefore,␈α∪the
␈↓ α,␈↓problem␈α∩splits␈α∩into␈α∩three␈α∩parts␈α∩-␈α∩moving␈α∩the␈α∩other␈α∩disks,␈α∩moving␈α∩the␈α∩bottom␈α∩disk,␈α∩and␈α∩moving
␈↓ α,␈↓the␈α∀others␈α∀again.␈α∀ Suppose␈α∀that␈α∀a␈α∀heuristic␈α∀is␈α∀used␈α∀that␈α∀can␈α∀recognize␈α∀this.␈α∀ Then␈α∀it␈α∀will␈α∀also
␈↓ α,␈↓recognize␈α⊂that␈α⊂each␈α⊂of␈α⊂the␈α⊂moves␈α⊂of␈α⊂␈↓↓n-1␈↓␈α⊂disks␈α⊂has␈α⊂the␈α⊂same␈α⊂character.␈α⊂ Thus␈α⊂there␈α⊂won't␈α⊂be␈α⊂any
␈↓ α,␈↓blind␈α⊃search␈α⊃of␈α⊃a␈α⊃space␈α⊃of␈α⊃3␈↓∧n␈↓␈α⊃points,␈α⊃but␈α⊃rather␈α⊃a␈α⊃direct␈α⊃problem␈α⊃reduction␈α⊃that␈α⊃will␈α⊃eventually
␈↓ α,␈↓involve␈α∀2␈↓∧n␈↓-1␈α∀trivial␈α∀moves.␈α∀ This␈α∀heuristic␈α∀does␈α∀not␈α∀explicitly␈α∀recognize␈α∀the␈α∀symmetries␈α∀of␈α∀the
␈↓ α,␈↓problem␈α↔that␈α↔permit␈α↔us␈α↔to␈α↔see␈α↔in␈α↔a␈α↔small␈α↔amount␈α↔of␈α↔reasoning␈α↔that␈α↔the␈α↔␈↓↓Tower␈α↔of␈α↔Hanoi␈↓␈α↔is
␈↓ α,␈↓solvable for any ␈↓↓n.␈↓

␈↓ α,␈↓␈↓ α|There␈α→is␈α→another␈α→heuristic␈α→that␈α→also␈α→solves␈α→the␈α→␈↓↓Tower␈α→of␈α→Hanoi␈↓␈α→problem.␈α→ Namely␈α→the
␈↓ α,␈↓conditions␈α∩for␈α∩moving␈α∩the␈α∩top␈α∩disk␈α∩are␈α∩null␈α∩and␈α∩it␈α∩can␈α∩be␈α∩moved␈α∩to␈α∩any␈α∩spike.␈α∩ Therefore,␈α∩its
␈↓ α,␈↓variable␈α∪can␈α∪be␈α∪given␈α∪an␈α∪arbitrary␈α∪value␈α∪without␈α∪changing␈α∪the␈α∪values␈α∪of␈α∪the␈α∪other␈α∪variables.
␈↓ α,␈↓This␈α⊃means␈α⊃that␈α⊃when␈α⊃the␈α⊃position␈α⊃of␈α⊃the␈α⊃top␈α⊃disk␈α⊃occurs␈α⊃in␈α⊃the␈α⊃condition␈α⊃for␈α⊃moving␈α⊃another
␈↓ α,␈↓disk,␈α∂this␈α∂part␈α∂of␈α∂the␈α∂condition␈α∂can␈α∂always␈α∂be␈α∂satis≡ed,␈α∂and␈α∂therefore␈α∂we␈α∂can␈α∂get␈α∂a␈α∂␈↓↓reduced␈α∂set␈α∂of
␈↓ α,␈↓↓transformations␈↓␈α⊂by␈α⊂eliminating␈α⊂the␈α⊂conditions␈α⊂on␈α⊂the␈α⊂top␈α⊂disk␈α⊂from␈α⊂the␈α⊂conjunctions.␈α⊂ However,
␈↓ α,␈↓in␈α∂this␈α∂reduced␈α∂set,␈α∂the␈α∂second␈α∂disk␈α∂will␈α∂enjoy␈α∂the␈α∂property␈α∂of␈α∂the␈α∂top␈α∂disk␈α∂in␈α∂the␈α∂previous␈α∂set␈α∂of
␈↓ α,␈↓transformations.  Successive application of this heuristic will wipe out the entire problem.

␈↓ α,␈↓␈↓ α|Let's␈α∩call␈α∩these␈α∩heuristics␈α∩the␈α∩␈↓↓bottom-up␈↓␈α∩and␈α∩␈↓↓top-down␈↓␈α∩heuristics␈α∩respectively.␈α∩ In␈α∩the␈α∩␈↓↓Tower
␈↓ α,␈↓↓of␈α∃Hanoi␈↓␈α∃case,␈α∃either␈α∃trivializes␈α∃the␈α∃problem,␈α∃and␈α∃one␈α∃might␈α∃suspect␈α∃they␈α∃are␈α∃equivalent.␈α∃ In
␈↓ α,␈↓general,␈α⊃it␈α⊃would␈α⊃seem␈α⊃that␈α⊃they␈α⊃are␈α⊂not␈α⊃equivalent␈α⊃but␈α⊃rather␈α⊃dual␈α⊃and␈α⊃correspond␈α⊃to␈α⊃problem
␈↓ α,␈↓reductions␈α≠much␈α≠used␈α≠in␈α≠human␈α≠problem␈α≠solving.␈α≠ Suppose␈α≠we␈α≠want␈α≠to␈α≠travel␈α≠from␈α≠San
␈↓ α,␈↓Francisco␈α∂to␈α∂Peking.␈α∂ Top-down␈α∂tells␈α∂us␈α∂that␈α∂when␈α∂we␈α∂have␈α∂to␈α∂change␈α∂planes␈α∂in␈α∂an␈α∂intermediate
␈↓ α,␈↓city,␈α⊗we␈α⊗will␈α⊗always␈α⊗be␈α⊗able␈α⊗to␈α⊗≡nd␈α⊗the␈α⊗gate␈α⊗of␈α⊗the␈α⊗outgoing␈α⊗plane,␈α⊗so␈α⊗we␈α⊗can␈α⊗eliminate␈α⊗the
␈↓ α,␈↓corresponding␈α∃variables␈α∃from␈α∃the␈α∃problem.␈α∃ Bottom-up␈α∃may␈α∃tell␈α∃us␈α∃that␈α∃the␈α∃main␈α∃problem␈α∃is
␈↓ α,␈↓getting␈α⊃the␈α⊃Chinese␈α⊃visa,␈α⊃and␈α⊃the␈α⊃problem␈α⊃can␈α⊃be␈α⊃divided␈α⊃into␈α⊃getting␈α⊃the␈α⊃visa␈α⊃and␈α⊃then␈α⊃using
␈↓ α,␈↓it.  In fact, the problem of getting to Peking has a more complex structure.




␈↓ α,␈↓α4. Reduction of Problems to Finite State

␈↓ α,␈↓␈↓ α|The␈α⊂blocks␈α⊂problem␈α⊂can␈α⊂be␈α⊂axiomatized␈α⊂in␈α⊂≡rst␈α⊂order␈α⊂logic␈α⊂as␈α⊂follows:␈α⊂We␈α⊂use␈α⊂the␈α⊂variable
␈↓ α,␈↓␈↓↓s␈↓␈α∪to␈α∪represent␈α∪states␈α∪of␈α∪the␈α∪world,␈α∪and␈α∪␈↓↓move(x,y,s)␈↓␈α∪to␈α∪represent␈α∪the␈α∪new␈α∪state␈α∪of␈α∪the␈α∪world␈α∪that
␈↓ α,␈↓results␈α⊂from␈α⊂moving␈α⊂the␈α⊂block␈α⊂␈↓↓x␈↓␈α⊂onto␈α⊂the␈α⊂block␈α⊂␈↓↓y␈↓␈α⊂when␈α⊂the␈α⊂world␈α⊂is␈α⊂in␈α⊂state␈α⊂␈↓↓s.␈↓␈α⊂(In␈α⊂the␈α⊂"situation
␈↓ α,␈↓calculus"␈α⊂of␈α⊂(McCarthy␈α⊂and␈α⊂Hayes␈α⊂1970),␈α⊂␈↓↓s␈↓␈α⊂is␈α⊂a␈α⊂situation␈α⊂variable).␈α⊂ Statements␈α⊂about␈α⊂one␈α⊂block
␈↓ α,␈↓being␈α⊃on␈α⊃top␈α⊃of␈α⊃another␈α⊃can␈α⊃be␈α⊃represented␈α⊃in␈α⊃two␈α⊃ways:␈α⊃one␈α⊃leads␈α⊃to␈α⊃Boolean␈α⊃search␈α⊃problems
␈↓ α,␈↓and␈α⊃the␈α⊃other␈α⊃leads␈α⊃to␈α⊃≡nite␈α⊃state␈α⊃search␈α⊃problems.␈α⊃ The␈α⊃≡rst␈α⊃is␈α⊃to␈α⊃introduce␈α⊃a␈α⊃relation␈α⊃␈↓↓on(x,y,s)␈↓
␈↓ α,␈↓asserting␈α⊂that␈α⊂the␈α⊂block␈α⊂␈↓↓x␈↓␈α⊂is␈α⊂on␈α⊂the␈α⊂block␈α⊂␈↓↓y␈↓␈α⊂in␈α⊂state␈α⊂␈↓↓s,␈↓␈α⊂and␈α⊂the␈α⊂second␈α⊂is␈α⊂to␈α⊂introduce␈α⊂a␈α⊂function
␈↓ α,␈↓␈↓↓support(x,s).␈↓ These are related by

␈↓ α,␈↓␈↓ α|∀␈↓↓x y s.(y = support(x,s) ≡ on(x,y,s)).␈↓

␈↓ α,␈↓The axioms for moving are

␈↓ α,␈↓␈↓ α|∀␈↓↓x y s.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)
␈↓ α,␈↓Finitary Search␈↓ 	␈↓αDraft␈↓␈↓ ∞September 5, 1989


␈↓ α,␈↓⊃ on(x,y,move(x,y,s)) ∧ ∀z.(z≠y ⊃ ␈↓λ-␈↓on(x,z,move(x,y,s))

␈↓ α,␈↓∧ ∀w z.(w≠x ⊃ on(w,z,move(x,y,s)) ≡ on(w,z,s)))

␈↓ α,␈↓using ␈↓↓on,␈↓ and

␈↓ α,␈↓␈↓ α|∀␈↓↓x y s.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)

␈↓ α,␈↓⊃ support(x,move(x,y,s)) = y ∧ ∀w.(w≠x ⊃ support(w,move(x,y,s)) = support(w,s))).

␈↓ α,␈↓If␈α∃we␈α∃admit␈α∃conditional␈α∃expressions␈α∃in␈α∃our␈α∃formalism␈α∃for␈α∃≡rst␈α∃order␈α∃logic,␈α∃the␈α∃second␈α∃axiom
␈↓ α,␈↓simpli≡es slightly to

␈↓ α,␈↓␈↓ α|∀␈↓↓x y s w.(x≠Table ∧ clear(x,s) ∧ (clear(y,s) ∨ y = Table)

␈↓ α,␈↓⊃ support(w,move(x,y,s)) = ␈↓αif␈↓↓ w=x ␈↓αthen␈↓↓ y ␈↓αelse␈↓↓ support(w,s)).␈↓

␈↓ α,␈↓The expression ␈↓↓clear(x,s)␈↓ which appears above is de≡ned by

␈↓ α,␈↓␈↓ α|␈↓↓∀x s.(clear(x,s) ≡ ∀z.␈↓λ-␈↓↓on(z,x.s))␈↓

␈↓ α,␈↓or

␈↓ α,␈↓␈↓ α|∀␈↓↓x s.(clear(x,s) ≡ ∀z.(support(z,s) ≠ x))␈↓.

␈↓ α,␈↓␈↓ α|These␈α_axioms␈α_are␈α_correct␈α_for␈α_the␈α_␈↓↓quasi-static␈↓␈α_block␈α_moving␈α_problem␈α_regardless␈α_of␈α_how
␈↓ α,␈↓many␈α⊃blocks␈α⊃there␈α⊃are.␈α⊃ To␈α⊃obtain␈α⊃a␈α⊃Boolean␈α⊃search␈α⊃or␈α⊃≡nite-state␈α⊃search␈α⊃problem,␈α⊃a␈α⊃person␈α⊃or
␈↓ α,␈↓computer␈α⊃program␈α⊃must␈α⊃make␈α⊃appropriate␈α⊃substitutions␈α⊃of␈α⊃a␈α⊃small␈α⊃≡nite␈α⊃number␈α⊃of␈α⊃blocks␈α⊃into
␈↓ α,␈↓the␈α∩axioms,␈α∩settle␈α∩on␈α∩an␈α∩initial␈α∩state␈α∩and␈α∩≡nal␈α∩condition␈α∩and␈α∩give␈α∩a␈α∩special␈α∩role␈α∩to␈α∩the␈α∩function
␈↓ α,␈↓␈↓↓move(x,y,s)␈↓ and to the variable ␈↓↓s␈↓ itself.

␈↓ α,␈↓␈↓ α|Such␈α⊂a␈α⊂process␈α⊂is␈α⊂analogous␈α⊂to␈α⊂trying␈α⊂to␈α⊂prove␈α⊂≡rst␈α⊂order␈α⊂logic␈α⊂problems␈α⊂by␈α⊂making␈α⊂a␈α⊂≡nite
␈↓ α,␈↓set␈α⊂of␈α⊂substitutions␈α⊂from␈α⊂the␈α⊂Herbrand␈α⊂universe␈α⊂into␈α⊂the␈α⊂axioms␈α⊂and␈α⊂then␈α⊂solving␈α⊂a␈α⊂problem␈α⊂in
␈↓ α,␈↓propositional␈α∀calculus.␈α∀ The␈α∀trick␈α∀in␈α∀either␈α∀case␈α∀is␈α∀to␈α∀≡nd␈α∀the␈α∀right␈α∀set␈α∀of␈α∀substitutions.␈α∀ Such
␈↓ α,␈↓methods␈α∀for␈α∀predicate␈α∀calculus␈α∀were␈α∀proposed␈α∀by␈α∀Martin␈α∀Davis,␈α∀and␈α∀he␈α∀experimented␈α∀with␈α∀a
␈↓ α,␈↓very␈α∩simple␈α∩form,␈α∩but␈α∩they␈α∩were␈α∩superseded␈α∩by␈α∩the␈α∩resolution␈α∩methods␈α∩that␈α∩don't␈α∩make␈α∩all␈α∩the
␈↓ α,␈↓substitutions at once.

␈↓ α,␈↓␈↓ α|In␈α⊃my␈α⊃opinion,␈α⊃the␈α⊃very␈α⊃fast␈α⊃algorithms␈α⊃that␈α⊃can␈α⊃be␈α⊃used␈α⊃after␈α⊃the␈α⊃substitutions␈α⊃have␈α⊃been
␈↓ α,␈↓made␈α⊃(e.g.␈α⊃the␈α⊃TAUT␈α⊃algorithm␈α⊃from␈α⊃FOL␈α⊃by␈α⊃Chandra␈α⊃and␈α⊃Weyhrauch)␈α⊃make␈α⊃it␈α⊃worthwhile
␈↓ α,␈↓to try to ≡nd heuristics for making a good set of substitutions.


␈↓ α,␈↓α5. Hardware

␈↓ α,␈↓␈↓ α|The␈α∂standard␈α∂algorithms␈α∂for␈α∂Boolean␈α∂and␈α∂≡nite␈α∂state␈α∂search␈α∂can␈α∂be␈α∂implemented␈α∂in␈α∂parallel
␈↓ α,␈↓hardware␈α~and␈α~should␈α~run␈α~extremely␈α~fast.␈α~ The␈α~idea␈α~is␈α~to␈α~have␈α~parallel␈α~simple␈α~processors
␈↓ α,␈↓generate␈α⊃points␈α⊃in␈α⊃the␈α⊃search␈α⊃space␈α⊃and␈α⊃compute␈α⊃neighbors␈α⊃in␈α⊃parallel␈α⊃and␈α⊃generate␈α⊃pointers␈α⊃to
␈↓ α,␈↓neighbors.␈α⊃ Then␈α⊃the␈α⊃distance␈α⊃from␈α⊃the␈α⊃initial␈α⊃point␈α⊃can␈α⊃propagate␈α⊃through␈α⊃the␈α⊃space,␈α⊃and␈α⊃the
␈↓ α,␈↓solution␈α∂path␈α∂will␈α∂be␈α∂found␈α∂in␈α∂a␈α∂number␈α∂of␈α∂stpes␈α∂proportional␈α∂to␈α∂the␈α∂length␈α∂of␈α∂the␈α∂shortest␈α∂path.
␈↓ α,␈↓Finitary Search␈↓ 	␈↓αDraft␈↓␈↓ ∞September 5, 1989


␈↓ α,␈↓We␈α∂envisage␈α∂such␈α∂parallel␈α∂hardware␈α∂as␈α∂a␈α∂satellite␈α∂to␈α∂a␈α∂conventional␈α∂computer␈α∂that␈α∂would␈α∂give␈α∂it
␈↓ α,␈↓parts␈α∂of␈α∂the␈α∂search␈α∂space␈α∂to␈α∂explore.␈α∂ In␈α∂the␈α∂design,␈α∂the␈α∂top-down␈α∂and␈α∂bottom-up␈α∂heuristics␈α∂must
␈↓ α,␈↓also be considered.

␈↓ α,␈↓␈↓ α|Naturally,␈α_much␈α_more␈α_must␈α_be␈α_learned␈α_about␈α_the␈α_algorithms␈α_for␈α_reducing␈α_problems␈α_to
␈↓ α,␈↓Boolean␈α"and␈α"≡nite-state␈α"searches,␈α"before␈α"one␈α"could␈α"seriously␈α"contemplate␈α"building␈α"such
␈↓ α,␈↓hardware.




␈↓ α,␈↓α6. Limitations

␈↓ α,␈↓␈↓ α|So␈α⊂far␈α⊂as␈α⊂I␈α⊂know,␈α⊂there␈α⊂aren't␈α⊂any␈α⊂signi≡cant␈α⊂AI␈α⊂problems␈α⊂that␈α⊂directly␈α⊂take␈α⊂a␈α⊂≡nitary␈α⊂form.
␈↓ α,␈↓This␈α⊃is␈α⊃because␈α⊃almost␈α⊃all␈α⊃intelligent␈α⊃behavior␈α⊃involves␈α⊃the␈α⊃application␈α⊃of␈α⊃general␈α⊃laws,␈α⊃even␈α⊃if
␈↓ α,␈↓only␈α∂the␈α∂laws␈α∂governing␈α∂the␈α∂e≥ects␈α∂of␈α∂moving␈α∂blocks,␈α∂to␈α∂particular␈α∂cases,␈α∂and␈α∂the␈α∂≡nitary␈α∂systems
␈↓ α,␈↓considered␈α in␈α this␈α paper␈α come␈α up␈α only␈α after␈α the␈α general␈α laws␈α have␈α been␈α instantiated.
␈↓ α,␈↓Therefore,␈α∃the␈α∃utility␈α∃of␈α∃the␈α∃method␈α∃depends␈α∃on␈α∃≡nding␈α∃ways␈α∃to␈α∃instantiate␈α∃the␈α∃general␈α∃laws
␈↓ α,␈↓before the search is made.

␈↓ α,␈↓␈↓ α|Another␈α_way␈α_of␈α_seeing␈α_the␈α↔limitations␈α_of␈α_≡nitary␈α_search␈α_is␈α_to␈α_try␈α_to␈α_apply␈α_it␈α_to␈α_games.
␈↓ α,␈↓Suppose␈α⊃there␈α⊃are␈α⊃only␈α⊃≡ve␈α⊃pieces␈α⊃left␈α⊃on␈α⊃a␈α⊃chess␈α⊃board.␈α⊃ Then␈α⊃we␈α⊃can␈α⊃use␈α⊃the␈α⊃locations␈α⊃of␈α⊃the
␈↓ α,␈↓pieces␈α∩as␈α∩variables,␈α∩so␈α∩the␈α∩position␈α∩is␈α∩characterized␈α∩by␈α∩the␈α∩values␈α∩of␈α∩≡ve␈α∩six-bit␈α∩quantities.␈α∩ So
␈↓ α,␈↓far so good since that will ≡t into one 36-bit machine word.

␈↓ α,␈↓␈↓ α|Another␈α∂matter␈α∂that␈α∂works␈α∂out␈α∂well␈α∂is␈α∂the␈α∂search␈α∂algorithm␈α∂itself.␈α∂ Instead␈α∂of␈α∂the␈α∂simple␈α∂tree
␈↓ α,␈↓search␈α⊗of␈α⊗the␈α⊗previous␈α⊗problems,␈α⊗we␈α⊗will␈α⊗need␈α⊗an␈α⊗α-β␈α⊗search,␈α⊗but␈α⊗this␈α⊗is␈α⊗helpful,␈α⊗because␈α⊗it
␈↓ α,␈↓reduces␈α⊂the␈α⊂size␈α⊂of␈α⊂the␈α⊂space␈α⊂to␈α⊂be␈α⊂searched.␈α⊂ The␈α⊂general␈α⊂search␈α⊂algorithm␈α⊂is␈α⊂di≥erent,␈α⊂but␈α⊂the
␈↓ α,␈↓successors calculation is just the application of a set of transformations.

␈↓ α,␈↓␈↓ α|The␈α↔≡rst␈α↔di≠culty␈α↔is␈α↔the␈α↔goal␈α↔condition.␈α↔ In␈α↔case␈α↔the␈α↔goal␈α↔is␈α↔checkmate,␈α↔the␈α↔number␈α↔of
␈↓ α,␈↓possible␈α∩goal␈α∩states␈α∩is␈α∩very␈α∩large,␈α∩and␈α∩they␈α∩are␈α∩not␈α∩summarized␈α∩by␈α∩giving␈α∩values␈α∩to␈α∩a␈α∩subset␈α∩of
␈↓ α,␈↓the␈α∩variables.␈α∩ However,␈α∩if␈α∩the␈α∩goal␈α∩were␈α⊃merely␈α∩to␈α∩promote␈α∩a␈α∩pawn,␈α∩the␈α∩goal␈α∩might␈α∩be␈α∩simply
␈↓ α,␈↓characterized.

␈↓ α,␈↓␈↓ α|The␈α∀real␈α∀di≠culty␈α∀is␈α∀that␈α∀there␈α∀would␈α∀be␈α∀too␈α∀many␈α∀transformations.␈α∀ There␈α∀would␈α∀be␈α∀at
␈↓ α,␈↓least␈α∂one␈α∂for␈α∂every␈α∂pair␈α∂consisting␈α∂of␈α∂an␈α∂initial␈α∂square␈α∂and␈α∂destination␈α∂square␈α∂for␈α∂each␈α∂piece,␈α∂i.e.
␈↓ α,␈↓about␈α∃5␈α∃x␈α∃64␈α∃x␈α∃10␈α∃=␈α∃3200.␈α∃ Actually␈α∃there␈α∃would␈α∃be␈α∃several␈α∃times␈α∃that␈α∃number,␈α∃because␈α∃the
␈↓ α,␈↓condition␈α∂for␈α∂moving␈α∂a␈α∂piece␈α∂from␈α∂a␈α∂given␈α∂square␈α∂to␈α∂a␈α∂given␈α∂other␈α∂square␈α∂might␈α∂require␈α∂several
␈↓ α,␈↓transformations.

␈↓ α,␈↓␈↓ α|I␈α∩can't␈α∩quite␈α∩convince␈α∩myself␈α∩that␈α∩the␈α∩formalism␈α∩couldn't␈α∩be␈α∩made␈α∩to␈α∩work␈α∩for␈α∩small␈α∩chess
␈↓ α,␈↓endgames,␈α⊃but␈α⊃it␈α⊃certainly␈α⊃wouldn't␈α⊃be␈α⊃very␈α⊃natural.␈α⊃ In␈α⊃fact,␈α⊃I␈α⊃believe␈α⊃it␈α⊃would␈α⊃work␈α⊃quite␈α⊃well
␈↓ α,␈↓for␈α⊂some␈α⊂␈↓↓go␈↓␈α⊂and␈α⊂checker␈α⊂end␈α⊂games.␈α⊂ In␈α⊂␈↓↓go␈↓␈α⊂problems␈α⊂where␈α⊂all␈α⊂the␈α⊂moves␈α⊂take␈α⊂place␈α⊂in␈α⊂a␈α⊂small
␈↓ α,␈↓region,␈α∪the␈α∪transformation␈α∪rules␈α∪may␈α∪be␈α∩reasonably␈α∪few,␈α∪but␈α∪the␈α∪goal␈α∪condition␈α∪may␈α∪be␈α∪rather
␈↓ α,␈↓di≠cult to compute.

␈↓ α,␈↓␈↓ α|To␈α∂the␈α∂extent␈α∂that␈α∂reduction␈α∂to␈α∂≡nitary␈α∂search␈α∂is␈α∂useful,␈α∂it␈α∂would␈α∂satisfy␈α∂some␈α∂people's␈α∂desire
␈↓ α,␈↓for␈α≠a␈α≠method␈α≠in␈α≠arti≡cial␈α≠intelligence␈α≠that␈α≠doesn't␈α≠come␈α≠from␈α≠natural␈α≠intelligence,␈α≠since␈α≠it
␈↓ α,␈↓depends␈α∩explicitly␈α∩on␈α∩a␈α∩computer's␈α∩ability␈α∩to␈α∩manipulate␈α∩bits␈α∩of␈α∩information␈α∩very␈α∩rapidly␈α∩once
␈↓ α,␈↓the meaning has been abstracted from them.
␈↓ α,␈↓Finitary Search␈↓ 	␈↓αDraft␈↓␈↓ ∞September 5, 1989


␈↓ α,␈↓αSearch of Cartesian product spaces.

␈↓ α,␈↓␈↓ α|There␈α∪is␈α∪a␈α∪small␈α∪general␈α∪theory␈α∩of␈α∪search.␈α∪ It␈α∪is␈α∪discussed,␈α∪for␈α∪example,␈α∪in␈α∪(Nilsson␈α∪19xx).
␈↓ α,␈↓Its␈α⊃concepts␈α⊃include␈α⊃depth-≡rst␈α⊃and␈α⊃breadth␈α⊃≡rst␈α⊃searches,␈α⊃and-or␈α⊃graphs,␈α⊃hill-climbing,␈α⊃and␈α⊃the
␈↓ α,␈↓α-β␈α⊂search␈α⊂method␈α⊂for␈α⊂game␈α⊂trees.␈α⊂ After␈α⊂this␈α⊂general␈α⊂theory,␈α⊂we␈α⊂have␈α⊂to␈α⊂get␈α⊂down␈α⊂to␈α⊂particular
␈↓ α,␈↓cases.

␈↓ α,␈↓␈↓ α|Suppose␈α∞that␈α∂the␈α∂search␈α∂space␈α∂has␈α∂a␈α∂Cartesian␈α∞product␈α∂structure,␈α∂and␈α∂most␈α∂search␈α∂spaces␈α∂do.
␈↓ α,␈↓The␈α_object␈α_of␈α_this␈α_section␈α_is␈α_to␈α_discuss␈α_some␈α_search␈α_methods␈α_that␈α_take␈α_advantage␈α_of␈α_some
␈↓ α,␈↓favorable␈α~conditions␈α~tha∨␈α~may␈α~obtain,␈α~i.e.␈α~we␈α~will␈α~try␈α~to␈α~≡nd␈α~su≠cient␈α~conditions␈α~for␈α~the
␈↓ α,␈↓applicability of the methods.
/FONT#0=BASL10[300,SYS]/FONT#1=BASI10[300,SYS]=∧∀≠≡∨ (),-.1=ABCDFHLRTabcdefghilmnopqrstuvwxyzz/FONT#2=BASB10[300,SYS]= ,.123456ABCDEFHIJLMNOPRSTUabcdefghilmnoprstuvwxyzz/FONT#3=SUB[300,SYS]=01234569LRnn/FONT#4=SUP[300,SYS]=1246nn/FONT#8=MISC25=--